package Sort;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-04-18 11:49
 */
public class QuickSort<T extends Comparable<T>> extends Sort<T> {
    private int partition(T[] nums,int l,int r){
        int i=l+1,j=r;
        T v=nums[l];
        while (true){
            while (less(nums[i],v)&&i!=r) i++;
            while (less(v,nums[j])&&j!=l) j--;
            if (i>=j){
                break;
            }
            swap(nums,i,j);
        }
        swap(nums,l,j);
        return j;
    }
    private void sort(T[] nums,int l,int r){
        if (r<=l) return;
        int p=partition(nums,l,r);
        sort(nums,l,p-1);
        sort(nums,p+1,r);
    }

    @Override
    public void sort(T[] nums) {
        sort(nums,0,nums.length-1);
    }

    public static void main(String[] args) {
        Integer[] nums={3,5,6,4,1,2};
        QuickSort<Integer> quickSort=new QuickSort<Integer>();
        quickSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
